package com.example.demo.suanfa_2tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 打印二叉树最大宽度
 */
public class TreeMaxWidthDemo {

    class Node {
        int value;
        Node left;
        Node right;
    }


    public void maxWidth(){
        Node head = new Node();

        int maxWidth = 0;
        int curWidth = 0;
        Node curEnd = null;
        Node nextEnd = null;

        // 层序遍历
        Queue<Node> queue = new LinkedList<>();
        if (head == null){
            System.out.println(0);
            return;
        }

        queue.add(head);
        curEnd = head;
        nextEnd = head;
        /**
         * 队列层序遍历整个二叉树
         * 1.存在头节点，入队，endNode = head  curWith = 1 nextEnd = head
         * 2.入队 当前节点 左右孩子，同时 curWidth ++ ， nextEnd 向后移动
         */
        while (!queue.isEmpty()){
            Node poll = queue.poll();

            if (poll.left!= null){
                queue.add(poll.left);
                nextEnd = poll.left;
                curWidth++;
            }

            if (poll.right!= null){
                queue.add(poll.right);
                nextEnd = poll.right;
                curWidth++;
            }

            if (poll == curEnd){
                maxWidth = Math.max(curWidth, maxWidth);
                curWidth = 0;
                curEnd = nextEnd;
                nextEnd = null;
            }
        }
    }







}
